package com.sicheng.lc.周赛.分类.栈.单调栈or单调队列;

import java.util.ArrayDeque;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 9:00
 */
@SuppressWarnings("all")
public class 子数组最小乘积的最大值 {
    //https://leetcode.cn/problems/maximum-subarray-min-product/
    static int mod = (int) (1e9 + 7);
    static int N = (int) 1e5;
    static int n;
    static int[] left = new int[N];
    static int[] right = new int[N];
    static long[] s = new long[N + 1];
    static ArrayDeque<Integer> deque = new ArrayDeque<>(N);


    public int maxSumMinProduct(int[] nums) {
        init(nums);

        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && nums[i] <= nums[deque.peek()]) {
                deque.pop();
            }
            if (!deque.isEmpty())
                left[i] = deque.peek() + 1;
            deque.push(i);
        }
        deque.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!deque.isEmpty() && nums[i] < nums[deque.peek()]) {
                deque.pop();
            }
            if (!deque.isEmpty())
                right[i] = deque.peek() - 1;
            deque.push(i);
        }

        long res = 0;
        for (int i = 0; i < n; i++) {
            int L = left[i] + 1, R = right[i] + 1;
            res = Math.max(res, (long) nums[i] * (s[R] - s[L - 1]));
        }
        return (int) (res % mod);
    }

    private void init(int[] nums) {
        deque.clear();
        n = nums.length;
        Arrays.fill(left, 0, n, 0);
        Arrays.fill(right, 0, n, n - 1);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];
        }
    }
}
